package com.shuzijun.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class ThreeSum {
    public static void main(String[] args) {
        Solution solution = new ThreeSum().new Solution();
        solution.threeSum(new int[]{-1,0,1,2,-1,-4});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            ArrayList<List<Integer>> result = new ArrayList<>();
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                if (i != 0 && nums[i] == nums[i - 1]) continue;
                int p = i + 1;
                int q = n - 1;
                while (p < q) {
                    if (p >= i + 2 && nums[p] == nums[p - 1]) {
                        p++;
                        continue;
                    }
                    if (q <= n - 2 && nums[q] == nums[q + 1]) {
                        q--;
                        continue;
                    }

                    int sum = nums[p] + nums[q];
                    if (sum == -1 * nums[i]) {
                        ArrayList<Integer> resultItem = new ArrayList<>();
                        resultItem.add(nums[i]);
                        resultItem.add(nums[p]);
                        resultItem.add(nums[q]);
                        result.add(resultItem);
                        p++;
                        q--;
                    } else if (sum < -1 * nums[i]) {
                        p++;
                    } else {
                        q--;
                    }
                }
            }
            return result;
        }

//    public List<List<Integer>> threeSum(int[] nums) {
//        Arrays.sort(nums);
//        ArrayList<List<Integer>> result = new ArrayList<>();
//        int n = nums.length;
//        HashMap<Integer, Integer> hashMap = new HashMap<>();
//        for (int i = 0; i < n; i++) {
//            hashMap.put(nums[i], i);
//        }
//
//        for (int i = 0; i < n; i++) {
//            if (i != 0 && nums[i] == nums[i-1]) continue;
//
//            for (int j = i+1; j < n; j++) {
//                if (j !=i+1 && nums[j] == nums[j-1]) continue;
//
//                int target = -1 * (nums[i] + nums[j]);
//                if (!hashMap.containsKey(target)){
//                    continue;
//                }
//                Integer k = hashMap.get(target);
//                if (k > j){
//                    ArrayList<Integer> resultItem = new ArrayList<>();
//                    resultItem.add(nums[i] );
//                    resultItem.add(nums[j] );
//                    resultItem.add(nums[k] );
//                    result.add(resultItem);
//                }
//            }
//
//        }
//        return result;
//    }
    }
//leetcode submit region end(Prohibit modification and deletion)

}